/*
	Richard Acosta
	March 10, 2008
	Recursive Decent Parcer - Java
	
	Grammar:
		E -> T + E | T - E | T
		T -> P * T | P / T | P
		P -> I | (E)
		I -> a | b | ... | y | z
	
*/
public class RDParser {

	
	public static void main(String[] args) {
		RDParser p = new RDParser("a+(c*d)"); // Fill this in.
	}
	
	public RDParser(String input) {
		if(matchE(input)) {
			System.out.println("The string \"" + input + "\" is in the language.");
		} else {
			System.out.println("The string \"" + input + "\" is not in the language.");
		}
	}
	
	public boolean matchE(String input) { // E -> T + E | T - E | T
		String temp[];
		// T + E
		temp = input.split("\\+",2);
		if(temp.length == 2 && matchT(temp[0]) && matchE(temp[1]))
			return true;
		
		// T - E
		temp = input.split("\\-",2);
		if(temp.length == 2 && matchT(temp[0]) && matchE(temp[1]))
			return true;
		
		// T
		if(matchT(input))
			return true;
		
		return false;
	}
	
	public boolean matchT(String input) { // T -> P * T | P / T | P
		String temp[];
		// P * T
		temp = input.split("\\*",2);
		if(temp.length == 2 && matchP(temp[0]) && matchT(temp[1]))
			return true;
		
		// P / T
		temp = input.split("\\\\",2);
		if(temp.length == 2 && matchP(temp[0]) && matchT(temp[1]))
			return true;
		
		// P
		if(matchP(input))
			return true;
		
		return false;		
	}
	
	public boolean matchP(String input) { // I | (E)
		// I
		if(matchI(input))
			return true;
		// (E)
		if(input.length() >= 3 && input.charAt(0) == '(' && input.charAt(input.length() - 1) == ')') {
			try {
				if(matchE(input.substring(1,input.length() - 1))) {
					return true;
				}
			} catch(Exception e) {  }
		}
		return false;		
	}
	
	public boolean matchI(String input) { // a | b | ... | y | z
		if(input.length() == 1 && input.charAt(0) >= 'a' && input.charAt(0) <= 'z')
			return true;
		return false;		
	}	
	
	
}
